package com.atguigui.leetcode1;

/**
 * 1053.交换一次的先前排列
 * Project: leetcode
 * Package: com.atguigui.leetcode1
 * Version: 1.0
 * <p>
 * Created by WJX on 2023/4/3 9:46
 */
public class P1053PreviousPermutationWithOneSwap {
    public static void main(String[] args) {
        Solution solution = new P1053PreviousPermutationWithOneSwap().new Solution();
        // TO TEST
    }

    class Solution {
        public int[] prevPermOpt1(int[] arr) {

            int n = arr.length;
            for (int i = n - 2; i >= 0; i--) {
                if (arr[i] > arr[i + 1]) {
                    //最后一个数开始
                    int j = n - 1;
                    //重复值选择其中下标最小的
                    while (arr[j] >= arr[i] || arr[j] == arr[j - 1]) {
                        j--;
                    }
                    int temp = arr[i];
                    arr[i] = arr[j];
                    arr[j] = temp;
                    //更换一次
                    break;
                }
            }
            return arr;
        }
    }
}
